#include <fstream>
#include <iostream>

using namespace std;

const int BOARD_WIDTH = 4;

// line[n][a] 表示 第n行中a号箭头出现的次数
int line[BOARD_WIDTH + 2][BOARD_WIDTH + 2] = {0};
// col [c][a] 表示 第n列中a号箭头出现的次数
int col [BOARD_WIDTH + 2][BOARD_WIDTH + 2] = {0};

// board[n][c]==a 表示[n,c]位置放置箭头a
int board[BOARD_WIDTH + 2][BOARD_WIDTH + 2] = {0};
int total_count = 0;

// 检查在[n,c]位置放置箭头arrow是否可行
bool isPlaceOK(int n, int c, int arrow)
{
    // 当前位置放置1(左上箭头)时，左侧不能是2，3；左上方不能是3(右下箭头)；正上方不能是3，4
    if (arrow == 1)
    {
        if (board[n-1][c-1] == 3)                           return false;
        if ((board[n-1][c] == 3) || (board[n-1][c] == 4))   return false;
        if ((board[n][c-1] == 2) || (board[n][c-1] == 3))   return false;
    }

    // 当前位置放置2(右上箭头)时，右上方不能是4(左下箭头)；正上方不能是3，4
    if (arrow == 2)
    {
        if (board[n-1][c+1] == 4)                           return false;
        if ((board[n-1][c] == 3) || (board[n-1][c] == 4))   return false;
    }

    // 当前位置放置4(左下箭头)时，左侧不能是2，3
    if (arrow == 4)
    {
        if ((board[n][c-1] == 2) || (board[n][c-1] == 3))   return false;
    }

    // 约束2:
    int partner = 0;
    if (arrow == 1)         partner = 2;
    else if (arrow == 2)    partner = 1;
    else if (arrow == 3)    partner = 4;
    else if (arrow == 4)    partner = 3;
    if (line[n][arrow] + line[n][partner] >= 2) return false;
    if (col [c][arrow] + col [c][5-arrow] >= 2) return false;

    return true;
}

void printSol()
{
    cout << "Solution: " << total_count << endl;
    for (int i = 1; i <= BOARD_WIDTH; ++i)
    {
        for (int j = 1; j <= BOARD_WIDTH; ++j)
        {
            if (board[i][j] == 1)         cout << "↖";
            else if (board[i][j] == 2)    cout << "↗";
            else if (board[i][j] == 3)    cout << "↘";
            else if (board[i][j] == 4)    cout << "↙";
            else   cout << "  ";
        }
        cout << endl;
    }
    cout << endl;
}

void PlaceArrow(int n, int c)
{
    if (n > BOARD_WIDTH)
    {
        total_count++;
        printSol();
        return;
    }

    // bool found = false;
    for (int arrow = 1; arrow <= BOARD_WIDTH; arrow++)
    {
        if (isPlaceOK(n, c, arrow))
        {
            // found = true;
            col [c][arrow]++;
            line[n][arrow]++;
            board[n][c] = arrow;
            if (c >= BOARD_WIDTH)
            {
                PlaceArrow(n + 1, 1);
            }
            else
            {
                PlaceArrow(n, c + 1);
            }
            board[n][c] = 0;
            col [c][arrow]--;
            line[n][arrow]--;
        }
    }
    // if (found) printSol();
}

int main()
{
    static std::ofstream g_log("result.txt");
    std::cout.rdbuf(g_log.rdbuf());

    PlaceArrow(1, 1);

    cout << "total: " << total_count << " solutions.\n";
    return 0;
}
